import java.util.Arrays;
import java.util.Stack;
//最小栈
class MinStack {
    public int val;
    private Stack<Integer> stack;
    private Stack<Integer> minstack;
    public MinStack() {
        stack = new Stack<>();
        minstack = new Stack<>();

    }
    int min = 0;
    public void push(int val) {
        stack.push(val);
        if(minstack.empty()){
            minstack.push(val);
        }else{
            if(minstack.peek() >= val){
                minstack.push(val);
            }
        }
    }

    public void pop() {
        if(!stack.empty()){
            Integer val  = stack.pop();
            if(val.equals(minstack.peek())){
                minstack.pop();
            }
        }
    }

    public int top() {
        if(!stack.empty()){
            return stack.peek();
        }
        return -1;
    }

    public int getMin() {
        return minstack.peek();
    }
}
public class Test {
    public static void main(String[] args) {

    }
    //判断有效括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(ch == '('||ch == '['||ch == '{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }else {
                    char ch1 = stack.peek();
                    if(ch1 == '('&&ch ==')'||ch1 == '['&&ch ==']'||ch1 == '{'&&ch =='}'){
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }
    //栈的压入、弹出序列
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0;i < pushA.length;i++){
            stack.push(pushA[i]);
            while (!stack.empty()&&j<popA.length&&stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    //逆波兰表达式
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String x: tokens){
            if(!isBudgetsymbols(x)){
                stack.push(Integer.parseInt(x));
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(x){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();

    }
    private boolean isBudgetsymbols(String x ){
        if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
            return true;
        }
        return false;
    }
}
